
//================v2要点总结===============
/**
 * 1. 思想：从上右下左四个方向进行 层序遍历（BFS,广度优先）查找染色。
 * 2. 注意：使用行列号就用行列号来表示，别用x,y,容易误解
 */

/**
 * @param {number[][]} image
 * @param {number} sr
 * @param {number} sc
 * @param {number} newColor
 * @return {number[][]}
 */
var floodFill = function (image, sr, sc, newColor) {
    // 如果一开始就是相同的直接返回
    let oldColor = image[sr][sc]
    if (oldColor === newColor) {
        return image
    }

    // 定义遍历方向: 上、右、下、左
    let dir = [[0, -1], [1, 0], [0, 1], [-1, 0]]
    let w = image[0].length
    let h = image.length

    // 广度优先遍历，借助队列,这里不再展开，就简单借助数组操作
    let queue = []
    queue.push([sr, sc])
    do {
        let p = queue.shift()
        // 染色
        image[p[0]][p[1]] = newColor
        for (let i = 0; i < dir.length; i++) {
            let nr = p[0] + dir[i][0]
            let nc = p[1] + dir[i][1]
            if (0 <= nr && nr < h && 0 <= nc && nc < w) {
                if (image[nr][nc] === oldColor) {
                    queue.push([nr, nc])
                }
            }
        }
    } while (queue.length)
    return image
};

console.log(floodFill([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2))
